package cn.zifangsky.queue.questions;

import cn.zifangsky.queue.Queue;
import cn.zifangsky.stack.LinkStack;
import cn.zifangsky.stack.Stack;
import org.junit.Test;

import java.util.function.Consumer;

/**
 * 如何使用两个栈来实现一个队列？
 *
 * @author zifangsky
 *
 */
class QueueWithTwoStacks<K extends Object> implements Queue<K> {
	private Stack<K> stack1;
	private Stack<K> stack2;

	public QueueWithTwoStacks() {
		stack1 = new LinkStack<>();
		stack2 = new LinkStack<>();
	}

	@Override
	public boolean isEmpty() {
		return stack1.isEmpty() && stack2.isEmpty();
	}

	@Override
	public int size() {
		return stack1.size() + stack2.size();
	}

	/**
	 * 入队：将数据压入stack1即可
	 * @时间复杂度 O(1)
	 * @param data
	 */
	@Override
	public void push(K data) {
		stack1.push(data);
	}

	/**
	 * 出队：
	 * 		1. 如果stack2不为空，则stack2执行出栈操作，并返回该出栈的数据即可
	 * 		2. 如果stack2为空，stack1不为空，则将stack1中的所有数据压入到stack2，接着stack2执行出栈操作
	 *      3. 如果stack2和stack1都为空，则抛出异常
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public K pop() {
		if(!stack2.isEmpty()){
			return stack2.pop();
		}else if(!stack1.isEmpty()){
			while (!stack1.isEmpty()) {
				stack2.push(stack1.pop());
			}

			return stack2.pop();
		}else{
			throw new RuntimeException("Queue Empty!");
		}
	}

	@Override
	public K top() {
		if(!stack2.isEmpty()){
			return stack2.top();
		}else if(!stack1.isEmpty()){
			while (!stack1.isEmpty()) {
				stack2.push(stack1.pop());
			}

			return stack2.top();
		}else{
			throw new RuntimeException("Queue Empty!");
		}
	}

	@Override
	public void clear() {
		stack1 = new LinkStack<>();
		stack2 = new LinkStack<>();
	}

	@Override
	public void print(Consumer<K> consumer) {
		stack2.print();
		stack1.print();
	}

	@Override
	public void deleteQueue() {
		stack1 = new LinkStack<>();
		stack2 = new LinkStack<>();
	}

}

public class Problem_002_TwoStacksImplementQueue {

	@Test
	public void testMethods() {
		Queue<Integer> queue = new QueueWithTwoStacks<>();
		queue.push(1);
		queue.push(2);
		queue.push(3);
		queue.push(4);

		queue.print(null);
		System.out.println();

		queue.pop();
		queue.pop();
		queue.pop();
		
		queue.push(5);
		queue.push(6);
		
		queue.print(null);
	}
}
